package com.gitee.feizns.explore.data_structure.union_find;

import java.util.HashMap;
import java.util.Map;

/**
 * @author feizns
 * @since 2020/3/13
 */
public class LongestConsecutive {

    public static void main(String[] args) {

    }

    public static int longestConsecutive(int[] num) {
        Uf uf = new Uf();
        for (int i : num) {
            uf.add(i);
            uf.union(i, i - 1);
            uf.union(i, i + 1);
        }
        return uf.sizes.values().stream().mapToInt(Integer::intValue).max().orElse(0);
    }

    static class Uf {
        Map<Integer, Integer> parents = new HashMap<>();
        Map<Integer, Integer> sizes = new HashMap<>();
        void add(int x) {
            if ( !parents.containsKey(x) ) {
                parents.put(x, x);
                sizes.put(x, 1);
            }
        }
        void union(int p, int q) {
            if ( parents.containsKey(p) && parents.containsKey(q) ) {
                int pr = find(p);
                int qr = find(q);
                if ( pr != qr ) {
                    parents.put(pr, qr);
                    sizes.put(qr, sizes.get(qr) + sizes.get(pr));
                }
            }
        }
        int find(int p) {
            if ( p != parents.get(p) )
                parents.put(p, find(parents.get(p)));
            return parents.get(p);
        }
    }

}
